// 离线 单调栈 线段树
// https://ac.nowcoder.com/acm/contest/34671/B
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 2e5;
const int maxn = 5 + 1e6;

int n, m;
int a[maxn];

struct Segtree {

  public:
    ll val[maxn << 2];
    int tag[maxn << 2];

  private:
    void maintain(int u) { val[u] = val[u << 1] + val[u << 1 | 1]; }
    void update_node(int u, int l, int r, ll x) { val[u] = (r - l + 1) * x, tag[u] = x; }
    void push_down(int u, int l, int r) {
        if (tag[u] == 0) return;
        int mid = l + r >> 1;
        update_node(u << 1, l, mid, tag[u]);
        update_node(u << 1 | 1, mid + 1, r, tag[u]);
        tag[u] = 0;
    }

  public:
    void bulid(int u, int l, int r) {
        if (l == r) {
            val[u] = a[l];
            return;
        }
        int mid = l + r >> 1;
        bulid(u << 1, l, mid);
        bulid(u << 1 | 1, mid + 1, r);
        maintain(u);
    }

    void update(int u, int l, int r, int s, int t, ll x) {
        if (s <= l && r <= t) {
            update_node(u, l, r, x);
            return;
        }
        push_down(u, l, r);

        int mid = l + r >> 1;
        if (s <= mid) update(u << 1, l, mid, s, t, x);
        if (t > mid) update(u << 1 | 1, mid + 1, r, s, t, x);
        maintain(u);
    }

    ll ask(int u, int l, int r, int s, int t) {
        if (s <= l && r <= t) return val[u];
        push_down(u, l, r);
        int mid = l + r >> 1;
        if (t <= mid) return ask(u << 1, l, mid, s, t);
        if (s > mid) return ask(u << 1 | 1, mid + 1, r, s, t);
        return ask(u << 1, l, mid, s, t) + ask(u << 1 | 1, mid + 1, r, s, t);
    }

} sg;

vector<int> sk;

struct ASK {
    int l, r, x;
    int id;
    ll ans;
    bool operator<(const ASK &r) const { return id < r.id; }
} ask[max_size];
bool cmp(const ASK &a, const ASK &b) { return a.x < b.x; }

int sk_maintain(int pos) {
    while (sk.size() > 1 && a[pos] >= a[sk.back()])
        sk.pop_back();
    int ret = sk.back() + 1;
    sk.push_back(pos);
    return ret;
}

int main() {
    n = rad();
    rf(i, n) a[i] = rad();
    m = rad();
    rf(i, m) ask[i].l = rad(), ask[i].r = rad(), ask[i].x = rad(), ask[i].id = i;
    sort(ask + 1, ask + 1 + m, cmp);
    sk.push_back(0);
    rf(i, m) {
        for (int pos = sk.back() + 1; pos <= ask[i].x; ++pos) {
            int l = sk_maintain(pos);
            sg.update(1, 1, n, l, pos, a[pos]);
        }
        ask[i].ans = sg.ask(1, 1, n, ask[i].l, ask[i].r);
    }
    sort(ask + 1, ask + 1 + m);
    rf(i, m) printf("%lld ", ask[i].ans);
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}